package tiruvury.InterviewPrep.Generic;

public class BitManipulation
{
	public static int computeSquareRoot(int num)
	{
		if (num >= 0)
		{
			if (num <= 1)
			{
				return num;
			}

			int low = 0;
			int high = num / 2 + 1;
			int mid;
			int pow;

			while (high - low > 1)
			{
				mid = (low + high) / 2;
				pow = mid * mid;

				if (pow == num)
				{
					return mid;
				}
				else if (pow > num)
				{
					high = mid;
				}
				else
				{
					low = mid;
				}
			}

			return low;
		}

		return -1;
	}

	/* Time: O(log b) */
	public static double computePower(double a, int b)
	{
		double base = a;
		int exp = b;

		if (base == 0)
		{
			return 0;
		}

		/*
		 * CODINGERROR: what ur returning is a double. But you previously
		 * declared result as int. That will give you a wrong rounded value.
		 */
		double result = 1;

		/*
		 * CODINGERROR: you forgot to get the abs value of exp. If exp is
		 * negative,
		 * the while loop will never execute!!
		 */
		exp = Math.abs(exp);
		while (exp > 0)
		{
			if ((exp & 1) == 1)
			{
				result = result * base;
			}

			base = base * base;
			exp = exp >> 1;
		}

		if (b < 0)
		{
			result = 1 / result;
		}

		return result;
	}

	public static String GetModifiedBinaryInput(String M, String N, int i, int j)
	{
		/*
		 * SYNTAX: Convert Binary String to integer: Integer.parseInt(String
		 * str, 2)
		 */
		int m = Integer.parseInt(M, 2);
		int n = Integer.parseInt(N, 2);
		int result = n;

		result = result >> (j + 1);
		result = result << (j + 1);
		result = result | (m << i);
		result = result | (((1 << i) - 1) & n);

		/*
		 * SYNTAX: Convert integer to Binary String: Integer.toBinaryString(num)
		 */
		return Integer.toBinaryString(result);
	}
}
